
'''
19. 删除链表的倒数第 N 个结点
'''
from typing import Optional

from com.siyuan.ListNode import ListNode


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 虚拟节点
        dummy = ListNode(0)
        dummy.next = head
        # 找到第n+1个节点
        node = self.getKthFromEnd(dummy, n + 1)
        # 删除
        node.next = node.next.next
        return dummy.next

    '''链表中倒数第k个节点'''
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        # 指针1
        p1 = head
        # 指针2
        p2 = head
        # 先移动p2 k次
        for i in range(k):
            p2 = p2.next

        # 同时移动p1\p2
        while p2:
            p1 = p1.next
            p2 = p2.next
        return p1